package com.shixianchen.review_the_day_before.day7;

import com.shixianjun.sort.Sortable;
import com.shixianjun.sort.SortableElement;

/**
 * @program: algorithm
 * @description: 归并排序
 * @author: SXC
 * @create: 2022-11-10 09:13
 **/
public class MergeSort implements Sortable {
    @Override
    public void sort(SortableElement[] arr) {

        //调取分组操作
        sortMerge(arr, 0, arr.length - 1);

    }

    /**
     * 分组
     *
     * @param arr
     * @param left
     * @param right
     */
    private void sortMerge(SortableElement[] arr, int left, int right) {
        //当只有一个数据时直接返回
        if (left == right) {
            return;
        }
        //获取中间值
        int mid = left + (right - left) / 2;

        //调取左半部分
        sortMerge(arr, left, mid);

        //调取右半部分
        sortMerge(arr, mid + 1, right);

        //归并操作
        merge(arr, left, mid + 1, right);
    }

    /**
     * 归并操作
     *
     * @param arr
     * @param leftPer
     * @param rightPer
     * @param rightBound
     */
    private void merge(SortableElement[] arr, int leftPer, int rightPer, int rightBound) {
        //分组数据
        int mid = rightPer - 1;

        //创建一个传递数组  4-0+1
        SortableElement[] temp = new SortableElement[rightBound - leftPer + 1];

        //左指针
        int i = leftPer;
        //右指针
        int j = rightPer;

        //传递数组指针
        int index = 0;
        //处理数据
        while (i <= mid && j <= rightBound) {
            if (arr[i].value <= arr[j].value) {
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }

        //当左面胜数据的时候
        while (i <= mid) {
            temp[index++] = arr[i++];
        }

        //当右面剩数据的时候
        while (j <= rightBound) {
            temp[index++] = arr[j++];
        }

        //将临时数据放入真正的数组
        for (int m = 0; m < temp.length; m++) {
            arr[leftPer + m] = temp[m];
        }
    }


}
